//二叉树最大宽度
//https://leetcode.cn/problems/maximum-width-of-binary-tree/

class Solution {
public:
    typedef pair<TreeNode*, unsigned int> PTI;
    int widthOfBinaryTree(TreeNode* root) 
    {
        unsigned int ret = 1;
        queue<PTI> q;
        q.push(make_pair(root,1));
        while(!q.empty())
        {
            int n = q.size();
            PTI left = q.front();
            PTI right = q.back();
            ret = max(ret,right.second - left.second + 1);
            while(n--)
            {
                PTI top = q.front(); 
                q.pop();
                if(top.first->left) q.push(make_pair(top.first->left,top.second * 2));
                if(top.first->right) q.push(make_pair(top.first->right,top.second * 2 + 1)); 
            }
        }
        return ret;
    }
};